1750B - Maximum Substring - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define float double
#define print1(p) cout<<p<<"\n";
#define print2(p,q) cout<<p<<" "<<q<<"\n";
#define print3(p,q,r) cout<<p<<" "<<q<<" "<<r<<"\n";
#define arrin(a,n) for(long long i=0;i<n;i++)cin>>a[i];

//fundamentals
#define pb push_back
#define pf push_front
#define lb(v,val)  (lower_bound(v.begin(),v.end(),val)-v.begin())
#define ub(v,val)  (upper_bound(v.begin(),v.end(),val)-v.begin())
#define line cout<<"\n";
#define sortv(v) sort(v.begin(),v.end())
#define sortvd(v) sort(v.begin(),v.end(),greater<int>())
#define lcm(a,b) (a*b/gcd(a,b))

//loops
#define f(i,a,b) for(int i=(int)a;i<(int)b;i++)
#define rf(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define f0 for(int i=0;i<n;i++)
#define f1 for(int i=1;i<=n;i++)
#define fr for(int i=n-1;i>=0;i--)

//some values
#define PI 3.14159265
const int MOD=1000000000+7;
const int MOD1 = 998244353;
const int Val9=1000000000;
const int Val6=1000000;

//maximum and minimum
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define max4(a,b,c,d) max(a,max3(b,c,d))
#define min4(a,b,c,d) min(a,min3(b,c,d))
#define endl "\n"
 
 
 int pwr(int x, int y, int mo){
 int r=1;
 while(y>0){
  if(y%2)
   r=(r%mo*x%mo%mo);
  x=(x%mo*x%mo)%mo;
  y/=2;
 }
 return r%mo;
}
 

vector<int>vprime;
void SieveOfEratosthenes(int n)
{
    bool prime[n+1];
    memset(prime, true, sizeof(prime));
 
    for (int p=2; p*p<=n; p++)
    {
        if (prime[p] == true)
        {
            for (int i=p*p; i<=n; i += p)
                prime[i] = false;
        }
    }
    for (int p=2; p<=n; p++)
    {  if (prime[p])
       {vprime.push_back(p);}
    }
}

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a%b);
}
 int nCr(int n, int r) 
{ 
    int ans=1;
    f(i,0,r)
    {
        ans*=n-i;
        ans/=i+1;
    }
    return ans;
}
void multiply(vector<vector<int>> &I, vector<vector<int>> &ARRAY, int no){
    vector<vector<int>> res(no,vector<int>(no));
    f(i,0,no){
        f(j,0,no){
            res[i][j]=0;
            f(k,0,no){
                int kuupuu=(I[i][k]*ARRAY[k][j])%MOD;
                res[i][j]=(res[i][j]%MOD+kuupuu)%MOD;
            }

        }

    }
    

    f(i,0,no){
        f(j,0,no){
            I[i][j]=res[i][j];
        }
    }

}

void powerofmatrix(vector<vector<int>> &ARRAY,int no, int mo){
    vector<vector<int>> I(no,vector<int>(no));
    f(i,0,no){
        f(j,0,no){
            if(i==j)I[i][j]=1;
            else I[i][j]=0;
        }
    }

    while (mo)
    { if(mo%2){
        multiply(I,ARRAY,no),mo--;
    }else{
        multiply(ARRAY,ARRAY,no), mo/=2;
    }
        
    }
    f(i,0,no){
        f(j,0,no){
            ARRAY[i][j]=I[i][j];
        }
    }
    

}
int coprimeton(int nope){
    int res=nope;
    for(int i=2;i*i<=nope;i++){
        if(nope%i==0)
        {res /= i;
        res *=(i-1);
        while(nope%i==0){
            nope=nope/i;
        }}

    }

    if(nope>1){
        res /=nope;
        res *=(nope-1);
    }
    return res;
}

int uchiha(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    int count0=0;
    int count1=0;
    for(int i=0;i<n;i++){
      if(s[i]=='1'){
        count1++;
      }else{
        count0++;
      }
    }
    int b=1;
    
    for(int i=0;i<n-1;i++){
        int j=i;
        int count=1;
        while(j<n and s[j]==s[j+1]){
          count++;
          j++;
        }
        b=max(b,count);
        i=j;
    }
    cout<<max(b*b,count0*count1)<<endl;
   
    return 0;
}



int32_t main() {
    // your code goes {here}
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    int tu=1;
    for(int i=0;i<t;i++){
       tu=tu+i;
    }
    while(t--){
        uchiha();
    }
    return 0;
}